<?php
/**
 * @title 315. 计算右侧小于当前元素的个数 - 二叉树
 * @author start2004
 */


class iTreeNode
{
    public $val = null;
    public $leftTreeCount = null;
    public $sameCount = null;

    public $left = null;
    public $right = null;

    function __construct($val = 0, $leftTreeCount = 0, $sameCount = 1, $left = null, $right = null)
    {
        $this->val = $val;
        $this->leftTreeCount = $leftTreeCount;
        $this->sameCount = $sameCount;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function countSmaller($nums) {
        /**
         * @since 2020-07-12 数组长度
         */
        $len = count($nums);
        if($len == 0){
            return [];
        } else {}

        /**
         * @since 2020-08-05 结果集
         */
        $result = [0];

        /**
         * @since 2020-08-05 根节点
         */
        $tree = new iTreeNode($nums[$len-1], 0, 1);

        /**
         * @since 2020-08-05 遍历
         */
        for($i=$len-2; $i>=0; $i--){
            $c = self::find($tree, $nums[$i], 0);
            // array_unshift($result, $c);
            $result[] = $c;
        }

        /**
         * @return
         */
        return array_reverse($result);
    }

    /**
     * @title 二叉树找到位置
     * @author start2004
     * @since 2020-08-05 Created
     *
     * @param $tree
     * @param int $num
     * @return integer
     */
    public function find(&$tree, $num = 0, $lessSum = 0){
        /**
         * @since 2020-08-05 节点值相同
         */
        if($num == $tree->val){
            $tree->sameCount += 1;
            return $tree->leftTreeCount+$lessSum;
        } elseif ($num < $tree->val){
            /**
             * @since 2020-08-05 左子树数量++
             */
            $tree->leftTreeCount += 1;

            /**
             * @since 2020-08-05 左节点
             */
            if($tree->left === null){
                $tree->left = new iTreeNode($num, 0, 1);
                return $lessSum;
            } else {
                return self::find($tree->left, $num, $lessSum);
            }
        } else {

            /**
             * @since 2020-08-05 右节点
             */
            if($tree->right === null){
                $tree->right = new iTreeNode($num, 0, 1);
                return $lessSum+$tree->leftTreeCount+$tree->sameCount;
            } else {
                return self::find($tree->right, $num, $lessSum+$tree->leftTreeCount+$tree->sameCount);
            }
        }
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.11_2.php
 */
$datas = [
    // [5,2,6,1],
    // [76,99,51,9,21,84,66,65,36,100,41], // [7, 8, 4, 0, 0, 4, 3, 2, 0, 1, 0]
    // [95,80,130,90,120,36,100,41], // [4,2,5,2,3,0,1,0]
    [375,1966,27,923,930,4358,796,3687,3383,1082,890,4455,1711,1594,2390,1391,1954,4164,3459,1912,802,3640,1703,1439,702,1756,270,469,468,3347,950,3023,1558,2775,4473,2861,3254,481,4488,1020,2217,3690,918,4107,317,2644,2185,2674,69,2794,4006,636,4113,2435,166,2692,372,3036,2264,3160,3394,4410,4197,3550,1199,4229,1317,1224,1476,4128,1982,3075,1196,2968,326,864,3976,589,2310,750,1950,3098,4393,4210,835,1274,2937,2504,1794,1858,3763,614,156,928,1037,971,4118,2342,559,2689,2135,1019,1342,3633,4310,4522,1217,2288,1117,1241,2003,2955,3022,3679,25,1936,1249,3059,3024,3602,3581,4541,3321,2119,3183,2850,2107,3006,4516,1789,3296,691,1714,916,1989,2539,396,3668,2634,2424,476,2285,1737,846,2931,3406,1698,886,148,3415,3762,893,1750,4559,1662,2328,3498,4005,98,2084,2339,140,252,931,3334,3158,2253,1399,4491,2959,2474,834,11,3369,322,3381,1676,595,3598,3566,1471,2626,330,2754,1683,3113,586,1646,1946,2489,3182,660,2347,3181,67,3361,2647,1746,3542,471,120,587,3532,3971,4406,4456,384,1637,3638,2616,2096,345,2703,630,3493,4086,2159,1125,2543,3883,2837,4298,994,1624,3890,4349,441,1260,3413,254,4414,463,2887,3780,2050,3429,150,2099,2588,291,301,79,2271,3605,3442,1905,3026,2843,4434,685,3485,2715,1064,2326,642,938,3205,4469,4564,4126,81,4173,607,2791,2846,2182,1303,3492,2468,1081,2414,2923,327,1055,3376,1209,1672,3123,3900,4237,4468,1520,1527,1378,3233,2705,296,2938,1935,2518,1349,3659,1626,2624,1416,1455,3328,1060,730,1841,2817,1449,1605,2105,3564,3619,3958,202,1213,4203,2490,1030,746,2894,1359,4287,851,4530,4543,1021,2799,4047,4489,3662,1052,2334,3715,3411,1228,3716,4450,2870,2661,434,1931,4326,3831,2356,2101,1360,2330,3403,1460,1659,3898,709,1203,160,2712,224,3533,3818,3748,972,2915,861,2379,4144,1981,785,2681,1661,668,2577,3648,2462,3370,3873,3247,1325,3647,4030,2996,2600,1924,3335,3691,2049,1657,3797,1443,278,243,2000,1706,2430,4160,716,4259,3804,1930,190,888,3964,680,966,1766,1132,379,830,2433,3199,2440,2380,2246,2704,467,2067,4245,2174,3434,4463,4404,1283,3157,1015,3224,2780,3791,2939,4200,2167,271,1689,3279,3104,1281,2926,2806,1183,3060,2746,4375,4567,2940,4252,925,4503,2453,1155,2751,313,3439,3650,3111,230,71,2298,4031,1320,1851,1097,3912,131,4097,3620,449,1304,1584,1431,554,2091,2867,3726,2208,1885,3202,2214,2314,1277,2245,2103,2972,3683,2092,1710,464,3583,3811,198,480,1556,2687,2171,4256,3342,4545,96,2536,4517,87,1123,2737,3332,1244,3824,1418,3723,1881,2516,2130,2541,1890,1762,260,176,3423,3299,3569,3310,1110,2757,1211,840,2262,1475,4309,4478,262,2327,3371,4367,356,363,13,1207,1306,1893,555,2048,1968,2696,1806,2614,461,2699,4508,3128,4438,1537,280,50,752,318,1590,2609,3921,848,4464,654,2477,3861,3677,2495,745,3217,1757,2883,4518,1188,3795,1453,1405,4335,2207,1263,3162,1461,4142,2437,4085,1171,1367,715,3905,1993,3013,1084,245,2552,4372,139,756,143,837,1243,1480,3146,2825,3758,867,729,425,3867,4318,3198,1728,1755,2402,1929,10,759,3760,2494,419,3255,1375,258,1918,410,3524,3626,1900,3124,4277,1348,1425,2912,399,1216,1422,2376,1916,2450,3250,3079,95,3705,1042,2668,2643,430,4162,2822,2537,2115,157,4344,259,2529,1780,444,4180,1412,873,366,2735,4432,3291,534,2547,725,526,2406,2151,1815,2280,3568,856,2753,2901,3776,3597,3931,509,2300,1365,56,3940,3398,3344,724,3674,240,3830,181,865,1127,3167,2046,3872,2381,354,1430,1029,1555,1990,4540,2149,4249,604,1628,1392,35,4262,3511,2445,4109,504,816,1479,580,3454,3727,3331,4121,2248,3034,4001,1478,130,1545,1557,4045,4408,4150,321,9,3249,2927,1776,2632,429,2464,4352,3681,591,3599,1693,3281,2587,256,4415,4575,4400,234,2441,3995,553,2431,4009,1419,860,1496,519,3821,3495,3585,819,4231,1691,747,2728,622,4555,450,513,351,2660,545,3580,1230,403,2962,2316,4401,1907,734,4454,776,810,179,2750,763,2102,3446,2812,2635,3552,188,3992,320,2581,2548,4074,2980,1301,1454,1548,2037,2778,2144,686,2378,1395,869,1938,3875,3194,3399,684,3773,2355,3545,3957,3330,3739,269,1681,3491,3077,2284,2834,2847,1819,2128,4487,806,2839,1134,2848,958,42,3218,1600,493,4161,1844,768,1870,3033,3222,1632,1645,4549,2423,1862,1690,2935,3536,4301,3955,2444,1615,207,1502,342,1328,3637,629,3392,1186,3922,1508,1561,4306,4043,1160,3019,1894,3948,4510,1827,90,3594,4425,4127,1108,1519,3043,4482,4244,3337,1820,2476,3531,3794,3751,3367,1358,2511,1565,4185,2294,2582,4537,3932,563,3855,3950,4433,1686,1614,3889,2447,316,408,3236,813,4572,3372,2036,2974,2318,2224,2659,2021,557,2241,2043,3209,3475,1254,1962,1658,3622,1452,616,2154,596,754,3697,2683,639,3142,4343,36,782,2044,896,2013,1648,2610,593,2352,827,2411,1688,626,3891,2146,1148,3144,135,400,294,2268,1976,4565,3164,2868,3956,2297,4562,581,3200,3808,72,3422,3420,3363,603,4227,1,3596,565,149,2482,3273,2783,2019,1261,3822,1170,1219,2531,3041,3559,833,1620,2664,4145,1992,995,3109,2137,2599,2745,609,1744,2343,550,1650,3487,4270,3929,3749,669,1111,281,3624,3203,2392,1877,4514,2990,60,4316,4388,4474,533,4148,3318,2967,1041,3608,1759,3460,4563,1493,1355,1467,496,3600,2478,906,883,3660,1231,2709,2321,640,2944,1880,1515,1289,332,3540,2085,4289,3359,766,1106,73,2919,52,333,4496,2878,2254,1343,4341,2796,4204,1882,4119,3671,3215,2220,170,136,4177,4288,1341,929,4140,2717,1118,2475,4108,3042,3915,1499,2562,2124,4356,2618,3341,1856,2744,3816,1335,1095,1474,663,3737,2615,2809,2296,4269,2999,2619,2827,2719,1242,871,1380,336,2183,897,3473,3980,3812,4569,3421,4090,2519,359,18,1940,3286,266,3118,4501,940,3259,445,97,205,3625,3101,338,2095,263,482,3274,32,2604,1368,1814,2235,921,1765,1610,3999,3802,2790,3769,4124,2810,3322,91,2694,2438,1156,3846,2597,3011,1846,2526,3051,675,3037,2259,1168,499,3590,3628,1377,3360,2305,443,1210,1390,2945,744,2961,4420,1730,1017,2350,610,4233,3431,1481,969,3876,651,520,2932,389,420,1860,4330,2969,3770,1552,3655,1063,3132,2178,1234,3631,1218,3272,1653,1917,1135,142,2930,786,99,300,4221,1926,1490,2646,3709,4397,1668,355,944,1272,1670,3884,1417,1330,2386,3357,4303,3537,4495,3641,165,3287,232,2397,3865,2031,1923,272,137,3445,1035,740,2897,1133,561,4398,2741,907,88,726,2675,2639,3874,4284,2527,666,2230,4312,1056,1597,741,401,2073,1743,3918,1027,2389,3702,412,329,3820,2394,201,3788,486,3646,340,2282,4247,1751,2432,3316,3402,2826,910,2083,4519,3591,273,2222,618,732,2056,4081,1521,3078,692,1120,3373,144,1654,1458,2918,4132,2273,3256,575,3522,2789,3653,86,1800,169,407,1201,2729,588,3002,3852,3474,1922,942,1872,3923,3488,16,246,2721,3397,3112,3185,1046,2165,58,1761,4424,852,2765,383,3593,3366,4146,3616,3365,3238,1910,2650,876,1457,2920,4557,106,2191,3700,3204,49,1902,1733,155,3565,3969,541,2558,4153,195,2933,2739,762,2893,3547,3197,3451,276,579,1162,268,3427,1429,1810,1739,4167,4123,547,3338,1869,3428,845,3539,1747,380,2421,1951,662,4436,4544,941,7,797,225,781,4525,1191,4165,3834,1150,770,1608,1482,4340,767,2005,1398,1440,2764,2215,1173,829,3282,4506,2040,3030,690,3180,3103,2290,153,1639,4116,3052,899,33,117,2824,4568,2484,2267,440,2779,3065,4479,889,2239,3377,2654,761,4311,3126,503,4391,378,3896,446,112,2362,1581,1136,2777,4285,3505,1128,1563,2534,2768,905,4327,1717,2637,3614,627,0,2071,3731,3754,2630,1003,1999,3275,210,3483,2560,839,2209,118,251,859,3008,1393,2396,983,1291,2917,774,1514,1093,3083,4429,2393,1809,1895,1197,151,1409,2636,514,2001,1491,2882,3230,3546,749,3994,1424,1044,1324,4504,2015,2244,3953,3651,3208,682,2434,293,516,1018,738,4466,807,2395,2469,2602,937,1469,220,1338,397,3333,2179,3981,922,2651,491,2879,2061,3156,4268,3556,2382,814,1406,3401,4294,885,2371,236,4099,2652,824,2164,1998,105,2162,4299,1187,3692,3826,4238,4149,714,2623,878,1090,1664,808,901,2364,2274,991,3312,2686,512,3907,352,158,4431,1680,3435,173,4402,2640,1811,3320,3939,3778,172,3879,4360,3151,2064,4206,1740,4049,1334,2116,392,681,647,2949,2250,4016,3379,634,287,1843,3449,1361,3799,2954,1749,1271,2,3772,163,3032,3881,2513,1509,956,4264,122,4480,94,2845,2774,373,4130,3246,4365,4201,357,847,501,613,965,1126,4207,2786,3317,66,3793,665,661,478,3528,1116,4189,1656,951,4137,2528,199,1969,1016,3190,775,4170,2658,655,433,2026,475,2304,3288,548,2010,1607,1773,439,3102,1813,3713,2677,2973,4199,3519,863,4033,2585,2307,1700,3039,953,4320,673,2740,1074,3324,2971,325,2601,1738,4071,2673,4061,103,2106,3095,1722,2108,3269,249,456,3092,2190,2914,2947,2532,4196,2960,2143,101,1865,4390,2642,3551,45,1140,2998,1536,695,3453,2922,960,3914,3894,3105,1113,3063,267,1366,4232,1411,3814,2525,1569,538,3525,24,4166,3179,3017,3166,20,4053,3358,442,3925,1838,694,2055,3510,3425,1238,979,551,1062,1043,1631,1959,3815,1004,3959,3910,1921,4036,2985,2859,4017,2787,679,2121,288,3988,2722,590,1551,3587,4072,3603,2814,2022,3038,2732,4323,912,290,4346,2784,2251,1671,2060,1786,2221,2924,2808,1530,3450,1718,385,2032,2265,1428,597,1010,3020,4051,1972,2035,769,517,3438,1080,1995,2451,488,842,1227,361,3949,2983,1801,2283,46,1772,4363,1310,2512,2175,1309,3058,3470,315,2247,2158,1927,3696,932,1571,2401,3509,4403,2148,773,2336,4526,2140,2797,1129,4422,489,3878,1373,3864,2908,4362,3133,1353,4228,3084,1583,1098,3817,2471,998,4485,1447,1787,1933,3693,406,4120,343,4028,200,2776,646,2598,3738,312,3790,710,2413,365,1883,4182,1066,4566,1103,2863,1206,3018,2278,3178,1531,2229,3975,4296,2024,494,3340,1053,1909,631,2802,1964,2361,1795,4125,2038,3007,2657,3886,1322,2584,4,4060,2340,3115,1526,4100,1986,4328,2303,2360,4492,4122,2986,1777,1630,3887,1864,962,2168,2858,2836,1396,3796,1267,3645,1622,704,3634,1507,2309,3302,1944,3571,186,2033,2535,908,1808,30,506,4198,3807,460,2896,1221,4034,1282,3768,1534,3979,3610,2463,1025,1667,4222,3781,1576,4236,866,3517,2081,111,209,3744,3116,1745,2698,1214,1313,3901,733,4442,4230,390,3433,2420,264,3266,1028,598,1154,2989,637,4490,2322,4457],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof(2);
foreach ($datas as $data){
    // var_dump($data);

    $obj = new Solution();
    $result = $obj->countSmaller($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
